redis为什么这么快-解决hash冲突的门道

redis中的全局哈希表和java中的hashmap一样都是使用链地址法解决hash冲突

链地址法:就是哈希桶算法,本身是一个数组,数组中的每一个元素是key和value的指针,value可以是任何类型,当出现hash冲突的时候,相同的kv在redis中指向同一个地址时,新插入的kv的next就会指向原来的kv,形成一个单向链表

解决hash冲突的散列算法主要有链地址法开放定址法再哈希法建立一个公共溢出区

image-20210714102609638

出现hash冲突后

image-20210714105441495

当这个链表越来越长,搜索指定的key的速度就会下降,当到达临界值时(redis规定的范围,类似于hashmap的加载因子)redis就会进行rehash(重新建表)

通俗的讲就是原来的a容器已经快要满了,就把新建一个b容器,容量是a容器的2倍

然后通过一些特殊的方法把a容器的数据全都放入b容器中,直到b容器完全覆盖a容器,则不再对a容器读写

redis采用的rehash是渐进式的,并不是一下子全部复制过去

  • 每次增删改查的时候都会把这些数据放在b中
  • 会启动定时任务把a中的冷key复制到b中

tips:redis中只要采用了hash表的结构的数据格式都会rehash